#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import os, sys
import copy

class CirecleExistsException(Exception):
    pass
    """
    def __init__(self, start, end):
        Exception.__init__(self)
        self.message = str(start) + " to " + str(end) + " already exist!"
    """

class Node:
    def __init__(self, node, number):
        self._node = node
        self._number = number

class DirectedGraph:
    def __init__(self):
        self._hasCircle = False
        self._graph = []
        # map store pairs: <node : number>, number is index in _graph
        self._nodeMap = {}
        # map store pairs: <number : node>, number is index in _graph
        self._numberMap = {}
        self._errorMessage = ""

    # 添加一条边
    def addDepend(self, start, end):
        if not start or not end:
            raise Exception("start node or end node is null")

        if start == end:
            raise Exception(str(start) + " and " + str(end) + " are the same")

        if not self._nodeMap.has_key(start):
            print("add node " + str(start))
            length = len(self._graph);
            self._nodeMap[start] = length
            self._numberMap[length] = start
            self.increaseGraph()

        if not self._nodeMap.has_key(end):
            print("add node " + str(end))
            length = len(self._graph);
            self._nodeMap[end] = length
            self._numberMap[length] = end
            self.increaseGraph()

        startNo = self._nodeMap[start]
        endNo = self._nodeMap[end]

        if self._graph[startNo][endNo] == 0:
            self._graph[startNo][endNo] = 1
        else:
            #self._errorMessage = str(start) + " and " + str(end) + "depends each other.";
            circle = self.getCircleDepences(startNo, endNo)
            message = "A dependency can not be added twice!\n"
            if circle:
                message = message + "Circle dependencies exists: "
                for i in circle:
                    message = message + " => " + str(i)
            #print message
            raise CirecleExistsException(message)

    def getCircleDepences(self, startNo, endNo):
        sccs = self.getStrongConnections()
        for scc in sccs:
            if self._numberMap[startNo] in scc and self._numberMap[endNo] in scc:
                return scc
        return []

    def increaseGraph(self):
        length = len(self._graph)
        # 每行添加一个0
        for i in range(length):
            row = self._graph[i]
            row.append(0);
        # 添加一行0，数量位lingth+1
        row = [0 for i in range(length+1)]
        self._graph.append(row)

    def getGraph(self):
        return self._graph

    def checkCircle(self):
        if self._errorMessage:
            raise CirecleExistsException(self._errorMessage)

    # 查找入度为0的node
    def getZeroInDegreeNodeNumber(self, graph, nodes):
        length = len(graph)
        # 查找矩阵的每一列
        for i in range(length): # column
            # if number already exist in nodes
            if i in nodes:
                continue
            zero = True
            for j in range(length): # row
                if graph[j][i] > 0: # in degree is not zero
                    zero = False
                    break;
            if zero:
                return i
        return -1


    def topologySortInternal(self, graph, nodes):
        length = len(graph)
        for i in range(length):
            num = self.getZeroInDegreeNodeNumber(graph, nodes)
            if num < 0:
                raise Exception("Out of column range!")
            row = graph[num]
            # 删除顶点num以及从该顶点出发的边
            for j in range(length):
                row[j] = 0;
            # 将该顶点加入序列
            nodes.append(num)


    def topologySort(self):
        self.checkCircle()
        newGraph = copy.deepcopy(self._graph)
        nums = []
        self.topologySortInternal(newGraph, nums)
        nodes = []
        for i in range(len(nums)):
            nodes.append(self._numberMap[nums[i]])
        return nodes


    def deepFirstSortInternal(self, no, visited, result):
        visited[no] = True
        result.append(self._numberMap[no])
        nodes = self._graph[no]
        for i in range(len(nodes)):
            if nodes[i] == 1 and not visited[i]:
                self.deepFirstSortInternal(i, visited, result)

    def deepFirstSort(self):
        visited = [False for i in range(len(self._graph))]
        result = []
        for i in range(len(visited)):
            if not visited[i]:
                self.deepFirstSortInternal(i, visited, result)
        return result

    def breadthFirstSortInternal(self, stack, visited, result):
        while len(stack) > 0:
            no = stack.pop(0)
            visited[no] = True
            result.append(self._numberMap[no])
            nodes = self._graph[no]
            for i in range(len(nodes)):
                if nodes[i] == 1 and not visited[i]:
                    stack.append(i)

    def breadthFirstSort(self):
        visited = [False for i in range(len(self._graph))]
        result = []
        for i in range(len(visited)):
            if not visited[i]:
                stack = [i]
                self.breadthFirstSortInternal(stack, visited, result)
        return result

    # 栈底的顶点访问结束时地址最晚
    def timeOrder(self, no, visited, stack):
        visited[no] = True
        nodes = self._graph[no]
        for i in range(len(nodes)):
            if nodes[i] == 1 and not visited[i]:
                self.timeOrder(i, visited, stack)
        stack.insert(0, no)

    # 转置矩阵
    def transpose(self):
        transposeGraph = DirectedGraph()
        transposeGraph._numberMap = copy.copy(self._numberMap)
        transposeGraph._nodeMap = copy.copy(self._nodeMap)
        transposeGraph._graph = copy.deepcopy(self._graph)
        length = len(self._graph)
        for i in range(length):
            for j in range(length):
                transposeGraph._graph[i][j] = self._graph[j][i]
        return transposeGraph

    """
    使用Kosaraju算法查找强连通子图：
    1. Let G be a directed graph and S be an empty stack.
    2. While S does not contain all vertices:
        Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v.
        Each time that depth-first search finishes expanding a vertex u, push u onto S.
    3. Reverse the directions of all arcs to obtain the transpose graph.
        While S is nonempty:
            Pop the top vertex v from S. Perform a depth-first search starting at v.
            The set of visited vertices will give the strongly connected component containing v;
            record this and remove all these vertices from the graph G and the stack S.
            Equivalently, breadth-first search (BFS) can be used instead of depth-first search.
    """
    def getStrongConnections(self):
        visited = [False for i in range(len(self._graph))]
        # step 1 of Kosaraju
        stack = []
        # step 2 of Kosaraju
        # 获取deep first sort
        for i in range(len(visited)):
            if not visited[i]:
                self.timeOrder(i, visited, stack)
        # step 3 of Kosaraju
        visited = [False for i in range(len(self._graph))]
        transposeGraph = self.transpose()
        subGraphs = []
        while len(stack) > 0:
            no = stack.pop(0)
            if not visited[no]:
                result = []
                transposeGraph.deepFirstSortInternal(no, visited, result)
                subGraphs.append(result)
        return subGraphs

if __name__ == "__main__":
    dg = DirectedGraph()
    dg.addDepend("5", "6")
    dg.addDepend("1", "2")
    dg.addDepend("1", "3")
    dg.addDepend("2", "4")
    dg.addDepend("3", "5")
    dg.addDepend("4", "6")
    dg.addDepend("6", "3")
    dg.addDepend("3", "5")
    print(dg._graph)

    sortList = dg.deepFirstSort()
    print("DFS: " + str(sortList))
    sortList = dg.breadthFirstSort()
    print("BFS: " + str(sortList))
    strongConns = dg.getStrongConnections()
    print("strong conns length: " + str(len(strongConns)))
    for conn in strongConns:
        print("strong connection:" + str(conn))

    #sortList = dg.topologySort()
    #print("Topology Sort: " + str(sortList))

